﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0048_Rob : IAlgorithm
    {
        // 打家劫舍

        // 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
        // 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

        // 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

        // 提示：
        //  1 <= nums.length <= 100
        //  0 <= nums[i] <= 400

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 3, 1, 1, 3 };
            // 算法执行与打印
            Console.WriteLine(Rob1(nums));
        }

        // 算法
        public int Rob(int[] nums)
        {
            var dp = new int[nums.Length, 2];
            dp[0, 0] = nums[0];
            dp[0, 1] = 0;
            for (int i = 1; i < nums.Length; i++)
            {
                dp[i, 0] = nums[i] + dp[i - 1, 1];
                dp[i, 1] = Math.Max(dp[i - 1, 0], dp[i - 1, 1]);
            }
            return Math.Max(dp[nums.Length - 1, 0], dp[nums.Length - 1, 1]);
        }

        // 空间优化
        public int Rob1(int[] nums)
        {
            var dp = new int[2];
            dp[0] = nums[0];
            dp[1] = 0;
            for (int i = 1; i < nums.Length; i++)
            {
                var temp = nums[i] + dp[1];
                dp[1] = Math.Max(dp[0], dp[1]);
                dp[0] = temp;
            }
            return Math.Max(dp[0], dp[1]);
        }
    }
}
